package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;

/**
 * SubTree 子树
 * Description:
 * You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes.
 * Create an algorithm to decide if T2 is a subtree of T1.
 * Test Cases：
 * ---------1                3
 * -------/ \              /
 * T1  = 2   3      T2 =  4
 * ---------/
 * --------4
 * <p>
 * ---------1               3
 * --------/ \               \
 * -- T1 = 2   3       T2 =    4
 * ----------/
 * ---------4
 * <p>
 * Output:
 * true
 * false
 * <p>
 * 思路:
 * 从根节点开始比较是否相同 不同则分别判断左右子树是否相同 类似于判断两树是否相同的问题{@link IdenticalTree}
 * Created by heqianqian on 2017/9/13.
 */
public class SubTree {

    public static void main(String[] args) {
        /*data preparation*/
        TreeNode root = new TreeNode(1);
        TreeNode rChild = new TreeNode(3);
        rChild.left = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = rChild;

        TreeNode subTree = new TreeNode(3);
        subTree.left = new TreeNode(4);

        SubTree st = new SubTree();
        boolean subtree = st.isSubtree(root, subTree);
        System.out.println(subtree);
    }

    /*
     * @param T1: The roots of binary tree T1.
     * @param T2: The roots of binary tree T2.
     * @return: True if T2 is a subtree of T1, or false.
     */
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if(T1==null && T2==null){
            return true;
        }
        if (T2 == null) {
            return true;
        }
        if (T1 == null) {
            return false;
        }
        if (isSameTree(T1, T2)) {
            return true;
        }
        return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
    }

    /**
     * judge T1 is same with T2
     */
    public boolean isSameTree(TreeNode T1, TreeNode T2) {
        if (T1 == null && T2 == null) {
            return true;
        }
        if (T1 == null || T2 == null) {
            return false;
        }
        if (T1.val != T2.val) {
            return false;
        }
        return isSameTree(T1.left, T2.left) && isSameTree(T1.right, T2.right);
    }
}
